⟸ Go Back ⟸

Exercise 17 (Homework 2).

(regular languages, prefixes, suffixes)

Prefixes and suffixes

Given a language L, define

\mathtt{Prefixes}(L)=\{w\mid \exists x\ (wx\in L)\}

and

\mathtt{Suffixes}(L)=\{w\mid \exists x\ (xw\in L)\}.

1. Given a DFA A, how can we construct a DFA to recognize the language \mathtt{Prefixes}(L(A))?

2. Given a DFA A, how can we construct a DFA to recognize the language \mathtt{Suffixes}(L(A))?